#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <cstdlib>
#include <stdlib.h>
#include <cstdio>
#include <cstdint>
#include <ctime>
#include <stack>
#include <string>
#include <queue>

using namespace std;

//Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<TreeNode*> test;
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        stack<TreeNode*> sta1;
        stack<TreeNode*> sta2;
        vector<vector<int>> vec;
        int dir = 0; //0-push from left to right; 1-push from right to left
        TreeNode* node = root;
        if (!node) return vec;
        sta1.push(node);
        while(1){
            vector<int> vecLine;
            while(!sta1.empty()){
                node = sta1.top();
                sta1.pop();
                vecLine.push_back(node->val);
                if (dir){
                    if (node->right){
                        sta2.push(node->right);
                    }
                    if (node->left){
                        sta2.push(node->left);
                    }
                }else{
                    if (node->left){
                        sta2.push(node->left);
                    }
                    if (node->right){
                        sta2.push(node->right);
                    }
                }
            }
            if (!vecLine.empty()){
                vec.push_back(vecLine);
                vecLine.clear();
            }
            dir = 1;

            // vector<int> vecLine;
            while(!sta2.empty()){
                node = sta2.top();
                sta2.pop();
                vecLine.push_back(node->val);
                if (dir){
                    if (node->right){
                        sta1.push(node->right);
                    }
                    if (node->left){
                        sta1.push(node->left);
                    }
                }else{
                    if (node->left){
                        sta1.push(node->left);
                    }
                    if (node->right){
                        sta1.push(node->right);
                    }
                }
            }
            if (!vecLine.empty()){
                vec.push_back(vecLine);
                vecLine.clear();
            }
            dir = 0;

            if (sta1.empty() && sta2.empty()){
                break;
            }
        }
        return vec;
    }
};

TreeNode* createTree(vector<string> vecStr)
{
    if (vecStr.empty()) return NULL;
    queue<TreeNode*> que;
    TreeNode* root;
    if (vecStr[0] != "null"){
        root = new TreeNode(atoi(vecStr[0].c_str()));
        que.push(root);
    }else{
        return NULL;
    }

    for (int i = 1; i < vecStr.size(); i++){
        if (!que.empty()){
            TreeNode* node = que.front();
            que.pop();
            //create left node
            if (vecStr[i] != "null"){
                node->left = new TreeNode(atoi(vecStr[i].c_str()));
                que.push(node->left);
            }
            i++;
            //create right node
            if (i < vecStr.size() && vecStr[i] != "null"){
                node->right= new TreeNode(atoi(vecStr[i].c_str()));
                que.push(node->right);
            }
        }else{
            break;
        }
    }
    return root;
}

vector<string> split(const string& s, const string& seperator) {
    vector<string> result;
    unsigned int posBegin = 0;
    unsigned int posSeperator = s.find(seperator);

    while (posSeperator != s.npos) {
        result.push_back(s.substr(posBegin, posSeperator - posBegin));// 
        posBegin = posSeperator + seperator.size(); // 分隔符的下一个元素
        posSeperator = s.find(seperator, posBegin);
    }
    if (posBegin != s.length()) // 指向最后一个元素，加进来
        result.push_back(s.substr(posBegin));

    return result;
}


int main()
{
    Solution su;

    su.test.push_back(createTree(split("3,9,20,null,null,15,7", ",")));
    su.test.push_back(createTree(split("3,9,20,null,null,20,7", ",")));

    for (int i = 0; i < su.test.size(); i++){
        vector<vector<int>> result = su.zigzagLevelOrder(su.test[i]);
        cout << "result is " << result[0][0] << endl;
    }
    return 0;
}
